CF1166E The LCMs Must be Large

思维好题，结论好题。

题意

一个长度为 \(n\) 的未知长度的序列，有 \(m\) 个限制，每个限制形如给定一个集合 \(S\) ，使集合内元素的 \(lcm\) 严格大于其补集元素的 \(lcm\) 。问是否存在这一序列。

思路

要注意我们是要尽可能使序列有解。

先给出结论：若所有集合两两间有交，则有解。否则一定无解。

首先有一个结论：若 \(A\subseteq B\)，那么 \(lcmB \geq lcmA\) 。

因为考虑 \(B\) 比 \(A\) 多的元素，只可能增加贡献而不可能减少贡献，所以上述结论显然。

然后我们回到题目：若一个限制的集合 \(A\) 与另一个限制的集合 \(B\) 不交，假设 \(lcmA>lcmA\setminus S\) (\(S\)表示整个序列集合)，那么一定有 \(B\subseteq A\setminus S\),即有 \(lcmA\setminus S\geq lcm B\) 。显然不符合要求。

然后证明结论的充分性。这里我们考虑一个构造的方法：假设所有元素初始都为1，我们将每个给定的集合内的元素都乘上一个互不相同的质数，那么如果集合两两相交，每个集合的\(lcm\)就是整个序列的\(lcm\)，并且每个集合的补集因为没有乘该集合的质数所以\(lcm\)一定小。如果有两个集合不相交，因为两个集合的质数不同，所以一定会出现一个集合的\(lcm\)大于另一个集合的情况，一定无解。

实现

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cctype>
#include<cstring>
#include<cmath>
#include<bitset>
using namespace std;
inline int read(){
	int w=0,x=0;char c=getchar();
	while(!isdigit(c))w|=c=='-',c=getchar();
	while(isdigit(c))x=x*10+(c^48),c=getchar();
	return w?-x:x;
}
namespace star
{
	const int maxn=1e4+10;
	int m;
	bitset<maxn> a[55],now;
	inline void work(){
		m=read();read();
	    for (int x,i=1;i<=m;i++) {
	        x=read();
	        while(x--)
	        	a[i].set(read());
	        for (int j=1;j<i;j++) {
	            if ((a[i] & a[j]).none())
					return (void)puts("impossible");
	        }
	    }
	    puts("possible");
	}
}
signed main(){
	star::work();
	return 0;
}